package com.hqq.exercise.tree;

/**
 * TreeClone 克隆二叉树
 * 题目描述:
 * 深度复制一个二叉树。
 * 给定一个二叉树，返回一个他的 克隆品
 * 样例输入:
 * 1
 * /  \
 * 2    3
 * / \
 * 4   5
 * 样例输出:
 * 相同结构的二叉树
 * Created by heqianqian on 2017/9/8.
 */
public class TreeClone {

    /**
     * @param root: The root of binary tree
     * @return root of new tree
     */
    public TreeNode cloneTree(TreeNode root) {
        // Write your code here
        if (root==null){
            return null;
        }
        TreeNode ct = new TreeNode(root.val);
        if (root.left!=null){
            ct.left = cloneTree(root.left);
        }
        if (root.right!=null){
            ct.right = cloneTree(root.right);
        }
        return ct;
    }

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(1);
        TreeNode lChild = new TreeNode(2);
        lChild.left = new TreeNode(4);
        lChild.right = new TreeNode(5);
        root.left = lChild;
        root.right = new TreeNode(3);

        TreeClone treeClone = new TreeClone();
        TreeNode node = treeClone.cloneTree(root);
        TreeNodeUtil.preOrderTraversal(root);
    }
}
